1039C - Network Safety - CodeForces Solution

               //  ॐ
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
typedef pair<int,int>       pii;
typedef pair<ll,ll>       pll;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
#define pb              push_back 
#define Sort(a)         sort(a.begin(),a.end())
#define ff                  first
#define ss                  second 
const int N = 5e5 + 10;
const ll f = 1e9 + 7;

ll binpow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % f;
        a = a * a % f;
        b >>= 1;
    }
    return res;
}

struct DSUrb {
    int sz; vi e; void init(int n) { e = vi(n+1,-1); sz = n; }
    int get(int x) { return e[x] < 0 ? x : get(e[x]); } 
    bool sameSet(int a, int b) { return get(a) == get(b); }
    int size(int x) { return -e[get(x)]; }
    vector<array<int,4>> mod;
    bool unite(int x, int y) { // union-by-rank
        x = get(x), y = get(y); 
        if (x == y) { mod.pb({-1,-1,-1,-1}); return 0; }
        if (e[x] > e[y]) swap(x,y);
        mod.pb({x,y,e[x],e[y]});
        e[x] += e[y]; e[y] = x; sz--; return 1;
    }
    void rollback() {
        auto a = mod.back(); mod.pop_back();
        if (a[0] != -1) e[a[0]] = a[2], e[a[1]] = a[3], sz++;
    }
};

void solve(){
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> ar(n+1,0);
    for(ll i = 1; i <= n; i++){
        cin >> ar[i];
    }
    map<ll,vector<array<ll,2>>> mp;
    for(ll i = 0; i < m; i++){
        ll a, b;
        cin >> a >> b;
        mp[ar[a] ^ ar[b]].pb({a,b});
    }
    ll ans = 0;
    DSUrb d; d.init(n);
    for(auto &[x, v]: mp){
        assert(x > 0);
        for(auto &[a, b]: v){
            d.unite(a, b);
        }
        ans += (binpow(2, d.sz) + f - binpow(2, n)); ans %= f;
        for(auto &[a, b]: v){
            d.rollback();
        } 
    }
    ans += (binpow(2,k) * binpow(2,n)) % f; ans %= f;
    cout << ans;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t=1;
    // cin>>t;
    while(t--)
        solve();
}